//***********************************简单选择排序***************************************
// 时间复杂度：O(n²)，空间复杂度O(1)
function simpleSelectSort(arr) {
  //arr.length-1 或 arr.length - 2 均可
  for (let i = 0; i <= arr.length - 2; i++) {
    let min = arr[i]
    let minIndex = i
    //循环找最小
    for (let j = i + 1; j <= arr.length - 1; j++) {
      if (arr[j] <= min) {
        min = arr[j]
        minIndex = j
      }
    }
    //交换
    let temp = arr[i];
    arr[i] = min
    arr[minIndex] = temp;
  }
}

// 测试用例
let arr = [21, 25, 49, 25, 16, 8]
simpleSelectSort(arr)
console.log(arr);



// 双指针优化
function priorSelectSort(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
      let min = arr[left];
      let max = arr[right];
      let minIndex = left;
      let maxIndex = right;
      for (let i = left + 1; i <= right - 1; i++) {
          if (arr[i] <= min) {
              minIndex = i;
              min = arr[i];
          }
          if (arr[i] > max) {
              maxIndex = i;
              max = arr[i]
          }
      }
      [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
      [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
      right--;
      left++;
  }
}
let arr = [4, 7, 3, 2, 8, 9, 5, 0, 1];
priorSelectSort(arr)
console.log(arr)



